package leetcode.code;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution282_1 implements IDebug {

	private int target;// 目标值
	private List<String> ans;// 答案
	private char[] nums;// num中间加空格
	private int len;// nums数组长度
	private char[] buffer;

	public List<String> addOperators(String num, int target) {
		ans = new ArrayList<>();
		if (num.length() == 1) {
			if (target == Integer.valueOf(num)) {
				ans.add(num);
			}
			return ans;
		}
		this.target = target;// 设置目标
		len = num.length();
		nums = num.toCharArray();
		buffer = new char[len << 1];
		// f(i,j,p)
		// 当前nums第i个位置, 决定i后加什么符号,
		// j是i位置开头数字开头在nums中的位置
		// p缓存在第几位
		f(0, 0, 0);
		return ans;
	}

	private void f(int i, int j, int p) {
		buffer[p] = nums[i];// 当前缓存追加字符
		if (Long.valueOf(new String(nums, j, i - j + 1)) > Integer.MAX_VALUE) {// 追加就越界, 无效
			return;
		}
		if (i == len - 1) {// 当i来到最后一位的时候
			this.checkAnswer(buffer, p);
			return;
		}
		if (nums[j] != '0') {// 开头不是0 ,后边允许不加符号
//			buffer[p + 1] = ' ';// 第i位后不放符号
			f(i + 1, j, p + 1);// 决定下一位, 继承开头, p + 1
		}
		buffer[p + 1] = '-'; // i位置后跟着 `-` 操作
		f(i + 1, i + 1, p + 2);// 决定下一位, 下一位是开头了, 由于多了一个符号 , 下一个位置 = p + 2
		buffer[p + 1] = '+';
		f(i + 1, i + 1, p + 2);
		buffer[p + 1] = '*';
		f(i + 1, i + 1, p + 2);
	}

	private void checkAnswer(char[] check, int len) {
		Stack<String> s = new Stack<>();
		StringBuffer cur = new StringBuffer();
		for (int i = 0; i <= len + 1; i++) {
			char c = check[i];
			if (c == '+' || c == '-' || c == '*' || i == len + 1) {
				if (!s.isEmpty() && s.peek().equals("*")) {
					s.pop();
					long num = Long.valueOf(s.pop());
					num *= Long.valueOf(cur.toString());
					if (num > Integer.MAX_VALUE) {
						return;// 数值超过int的是错的
					}
					s.add(String.valueOf(num));
				} else {
					long l = Long.valueOf(cur.toString());
					if (l > Integer.MAX_VALUE) {
						return;// 数值超过int的是错的
					}
					s.add(String.valueOf(l));
				}
				if (i == len + 1)
					break;
				s.add(String.valueOf(c));
				cur.setLength(0);
				continue;
			}
			if (c == ' ')
				continue;
			if (c >= '0' && c <= '9') {
				cur.append(c);
				continue;
			}
		}
		int ans = 0;
		int last = 0;
		while (!s.isEmpty()) {
			String c = s.pop();
			if (c.equals("+")) {
				ans += last;
			} else if (c.equals("-")) {
				ans -= last;
			} else {
				last = Integer.valueOf(c);
			}
		}
		ans += last;
		if (ans == target) {
			this.ans.add(new String(check, 0, len + 1));
		}
	}

	public static void main(String[] args) {
		Solution282_1 so = new Solution282_1();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
		so.debug6();
	}

	@Override
	public void debug1() {
		String num = "123";
		int target = 6;
		String str = "[\"1+2+3\", \"1*2*3\"]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug2() {
		String num = "232";
		int target = 8;
		String str = "[\"2*3+2\", \"2+3*2\"]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug3() {
		String num = "00";
		int target = 0;
		String str = "[\"0+0\", \"0-0\", \"0*0\"]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug4() {
		String num = "105";
		int target = 5;
		String str = "[\"1*0+5\",\"10-5\"]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

	public void debug5() {
		String num = "3456237490";
		int target = 9191;
		String str = "[]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

	public void debug6() {
		String num = "9999999999";
		int target = 1409865409;
		String str = "[]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

}
